package 线段树And树状数组;

import java.util.Arrays;
/**
 * 
 * 能用树状数组 
 * 就用 树状 数组
 * 
 * 只要 树状数组 能 ac  就不用线段树 
 * 因为 线段树的代码 很长
 * 是在 没办法的时候 再去 用线段树吧
 * 
 * 
 * 
 * @author I adore you
 *
 */
public class 树状数组 {
	
		public static void main(String []args) {
			int arr [] = {0,0,0,0};
			ArrayTree arrTree = new ArrayTree(arr);
			int sum = arrTree.query(arr.length - 1);
			System.out.println(sum);
//			System.out.println(Arrays.toString(arrTree.nums));
//			System.out.println(Arrays.toString(arrTree.sums));
//			arrTree.insert(1, 4);
//			arrTree.update(1, 0);
			arrTree.addScale(0, arr.length - 1, 2);
			arrTree.updateScale(0, arr.length - 1, 4);
			System.out.println(Arrays.toString(arrTree.nums));
			System.out.println(Arrays.toString(arrTree.sums));
			System.out.println(arrTree.query(3));
		}
	
	
}
/**
 * 树状数组的    相应题目的 讲解 
 * https://leetcode-cn.com/problems/range-sum-query-mutable/solution/-by-hu-ge-8-t4rn/
 * @author I adore you
 *
 */
class ArrayTree{
	
	/*
	 * int N;
	 * int origion = new int [N];
	 * 千万不要 出现 这种沙雕的 操作 
	 * N 就不没有 赋值 之前 
	 * 上面的 那个 就相当于 new   int [0];
	 * 智障操作
	 */
	
	
	
	
	/**
	 * 由输入 的 数组 而 转换成 当前 结构中的 
	 * 数组 
	 * 注意这个 nums 数组 并没有  做   ＋ 1 处理 有效下 标 还是从 0开始 的 
	 * 这点 还是 需要 注意下的 
	 */
	int nums[];
	/**
	 * 累加和 数组 但是 这个 累加和 
	 * 和 你理解的 累加和 数组 又不太 一样 的 那种
	 * 但是 这个 sums  数组  是 进行了 + 1 处理的
	 * 有效下标 是从 1  开始  
	 * 这样处理 的 有很多种原因 
	 * 慢慢 体会  
	 */
	int sums[];
	public ArrayTree(int nums[]) {
//		this.nums = nums;
		this.nums = new int[nums.length];
		this.sums = new int[nums.length + 1];
		for(int i = 0;i < nums.length;i++) {
			insert(i,nums[i]);
		}
	}
	/**
	 * 实际上其主要功能是: 找到x的二进制数的最后一个1所表示的二进制
		换句话说,就是lowbit(x)的值必然是2的幂次(最高位为1,其他位为0)
		lowbit(x) = 2^{(k)}
		lowbit(x)=2 (k)

	 */
	public int lowbit(int x) {
		return x & -x;
	}
	/**
	 * 这个 insert 函数的 功能其实 
	 * 不仅仅 能初始化 这个 <树状数组> 
	 * 我感觉 还可以  进行 进行 某个 区间的   add   功能
	 */
	public void insert (int index,int value) {
		int x = index + 1;
		while(x < sums.length) {
			sums[x] += value;
			x += lowbit(x);
		}
		/**
		 * 这里 就是 修改 原 数组中的数据 
		 * 在 原来 数据的 基础上 直接加上 value;
		 */
		nums[index] +=value;
	}
	public void update(int index,int value) {
		int x = index + 1;
		while(x < sums.length) {
			sums[x] = sums[x] - nums[index] +value;
			x += lowbit(x);
		}
		/**
		 * 注意 这是 直接修改 index 位置 上的 值 为 value
		 * 所以 原数组 中 index  下标上 的 值 就不要了 所以  直接 赋值 
		 */
		nums[index] = value;
	}
	/**
	 * 这个 query  相当于 是 前缀和
	 * 这个 树状数组 还 蛮吊的 说实话 
	 * 能 扯到 很多的 知识 
	 * 举个 例子:
	 * query(7) = preSum(7) = sums[7] + sums[6] + sums[4]
	 * 这里 注意 7 对应着 是原数组 中的 下标 6
	 * 因为 sums  数组的 下标 进行 了  加 1 处理 
	 * 
	 * 
	 * 这里 有时间 还是 要去 研究 一下 前缀和 
	 * 和 差分 数组 这些 东西的 
	 * 这里 的对 前缀和 和 原数组 index 下标的  理解  还是不够 深刻的
	 * @param x
	 * @return
	 */
	public int query(int index) {
		int x =index + 1; 
		int ans  = 0;
	    while(x != 0) {
	    	ans += sums[x];
	    	x  -= lowbit(x);
	    }
	    return ans;
	}
	/**
	 * 求区间和  的 
	 * 注意 这里 sum 函数的函数 体调用 中 传入的 
	 * <参数>  
	 * @return
	 * 参数的 left 和 right 是原数组 的下标 
	 */
	public int sum(int left,int right) {
		
		return query(right) - query(left - 1);
	}
	
	
	
	
	/**
	 * 下面 是 宫水三叶的 代码  写的 是 真 不错 
https://leetcode-cn.com/problems/range-sum-query-mutable/solution/guan-yu-ge-lei-qu-jian-he-wen-ti-ru-he-x-41hv/
	 *上面的 只是用   于 单点修改  
	 * 就是 只修改 原数组 中 的 一个 位置 
	 * 其实 也可以 进行区间的 修改 下  面 就是 进行 区间的 修改操作
	 * 直接来个  for循环 呗 重复 操作 
	 * 其实没有什么
	 */
	public void addScale(int left,int right,int value) {
		for(int i = left; i <= right;i++) {
			insert(i,value);
		}
	}
	public void updateScale(int left,int right,int value) {
		for(int i = left; i <= right;i++) {
			update(i,value);
		}
	}
	/**
	 * 为啥 说  进行 单点操作的 时候
	 * 树状数组 是 不二之选
	 * 因为 代码 量 相较于  线段  图.树 要 小 很多
	 * 
	 * 但 要 进行 区间修改的 时候 
	 * 注意 这里 树状 数组 采用的 是 for 循环 遍历 的 方式
	 * 重复 进行 insert  和 update 操作 
	 * 这个 过程   不一定 有 线段 图.树 快
	 * 这个 跟  数据规模 有关系
	 */
}